#include <iostream>
#include <list>
#include <unordered_map>
#include <utility>

using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {

    }

    void put(int key,int value){
        auto it = _cache.find(key);
        if(it != _cache.end()){
            it->second->second = value;
            _nodes.splice(_nodes.begin(),_nodes,it->second);
        }else{
            if(_nodes.size() == _capacity){
                auto deleteNode = _nodes.back();
                _nodes.pop_back();
                _cache.erase(deleteNode.first);
            }
            _nodes.push_front({key, value});
            _cache[key] = _nodes.begin();
        }
    }
    int get(int key)
    {
        auto it = _cache.find(key);
        if(it == _cache.end())
        {
            return -1;
        }
        else
        {
            _nodes.splice(_nodes.begin(), _nodes, it->second);
            return it->second->second;
        }
    }

    void print() const
    {
        for(auto &elem : _nodes)
        {
            cout << "(" << elem.first 
                << ", " << elem.second
                << ")";
        }
        cout << endl;
    }

private:
    int _capacity;
    list<pair<int,int>> _nodes;
    unordered_map<int,list<pair<int,int>>::iterator> _cache;

};

void test(){

    LRUCache lru(5);

    lru.put(1, 10);
    lru.print();

    cout << endl;
    lru.put(2, 20);
    lru.print();

    cout << endl;
    lru.put(3, 30);
    lru.print();

    cout << endl;
    cout << "lru.get(2) = " << lru.get(2) << endl;
    lru.print();

    cout << endl;
    lru.put(4, 40);
    lru.print();
}

int main()
{
    test();
    return 0;
}

